'''
https://leetcode.cn/problems/course-schedule-ii/description/
'''
from collections import deque, defaultdict
from typing import List


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 邻接表建 有向图
        table = [[] for _ in range(numCourses)]
        # 入度表
        indegrees = [0 for _ in range(numCourses)]
        for v, u in prerequisites:
            table[u].append(v)
            indegrees[v] += 1       # v的入度+1

        q = deque()     # 先进先出，比如右进左出
        for i, indegree in enumerate(indegrees):
            if indegree == 0:
                q.append(i)
        res = []
        while q:
            u = q.popleft()
            for v in table[u]:
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    q.append(v)
            res.append(u)
        return res if len(res) == numCourses else []


    def canFinish(self, n: int, edges: List[List[int]]) -> bool:
        graph = [[] for _ in range(n)]
        indegrees = [0 for _ in range(n)]
        for v, u in edges:
            graph[u].append(v)
            indegrees[v] += 1
        q = [0 for _ in range(n)]
        l, r = 0, 0
        for i, indegree in enumerate(indegrees):
            if indegree == 0:
                q[r] = i
                r += 1
        while l < r:
            u = q[l]
            l += 1
            for v in graph[u]:
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    q[r] = v
                    r += 1
        return l == n